package J1128;

public class MySingleList implements IList {
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    @Override
    public void addFirst(int data) {

    }

    @Override
    public void addLast(int data) {

    }

    @Override
    public void addIndex(int index, int data) {

    }

    @Override
    public boolean contains(int key) {
        return false;
    }

    @Override
    public void remove(int key) {

    }

    @Override
    public void removeAllKey(int key) {

    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void clear() {

    }

    @Override
    public void display() {

    }

    public ListNode FindPrevKey(int key) {
        ListNode prev = head;
        while(prev.next != null) {
            if(prev.next.val == key)
                return prev;
            else
                prev = prev.next;
        }
        return null;
    }

    public ListNode RemoveAll(int key) {
        if(head == null)
            return null;
        ListNode prev = head;
        ListNode cur = prev.next;
        while(cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == key)
            head = head.next;
        return cur;
    }

    //翻转链表
    public  ListNode reverseList() {
        if(head == null)
            return null;
        if(head.next == null)
            return null;
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    //寻找中间结点
    public ListNode FindMid() {
        ListNode slow = head;
        ListNode fast = slow;
        //两个条件不能互换  分别对应奇偶情况
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //寻找倒数第k个结点
    public ListNode FindFinalK(int K) {
        if(K <= 0)
            return null;
        ListNode slow = head;
        ListNode fast = head;
        while(K > 0){
            if(fast.next == null)   //说明K太大了
                return null;
            fast = fast.next;
            K--;
        }
        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    //编写代码，以给定值X为基准将链表分割为两部分
    //所有小于x的结点排在大于或等于x的结点之前
    //且不能改变原本的数据顺序
    public ListNode partition(ListNode listNode , int x) {
        //as 放比x大的 bs放比x小的
        if(listNode == null) {
            return null;
        }
        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;
        ListNode cur = head;
        while(cur != null) {
            if(cur.val < x) {
                if(bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next= cur;
                    be = be.next;
                }
            } else {
                if(as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if(bs == null) {
            bs = as;
        }
        if(ae.next != null) {
            ae.next = null;
        }
        bs.next = as;
        return bs;
    }

    //链表的回文结构
    //思路：找出中间结点 将后半部分链表翻转 然后对比
    public boolean chkPalindrome() {
        if(head == null)
            return true;
        ListNode slow = head;
        ListNode fast = head;
        //1、找中间结点
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //2、翻转
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3、往中间找
        while(slow != head) {
            if(slow.val != head.val)
                return false;
            if(head.next == slow)  //如果是偶数 就需要判断这种情况
                return true;
            slow = slow.next;
            head = head.next;
        }
        return true;
    }

    //判断两个链表是否相交
    //思路：1、求长度
    //     2、走差值步 然后一步步往后走 在哪里相遇哪里就是共同点
    public ListNode ll(ListNode A ,ListNode B) {
        int lenA = 0;
        int lenB = 0;
        ListNode pl = A;
        ListNode ps = B;
        //分别求长度
        while (A != null) {
            lenA++;
            A = A.next;
        }
        while (B != null) {
            lenB++;
            B = B.next;
        }
        int len = lenA - lenB;
        if(len < 0) {
            pl = B;
            ps = A;
            len = -len;
        }
        //走不同步数
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        while(pl != null && pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == ps && pl == null) {
            return null;
        }
        //如果两个不相等都走到了null 刚好不执行循环 返回null
        return pl;
    }

    //判断链表是否有环
    public boolean hasCycle() {
        ListNode slow = head;
        ListNode fast = head;
         while(fast != null && fast.next != null) {
             fast = fast.next.next;
             slow = slow.next;
             if(fast == slow)
                 return true;
         }
         return false;
    }

    //给一个链表 找到环的入口点
    //通过计算可知：相遇点到入口点的距离和起始点到入口点的距离相同
    //            可以一个从起始点出发 一个从相遇点出发 相遇的地方就是入口点
    //              X = (N - 1)*C + Y
    public ListNode WhereCycle() {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
